﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GistDescriptor.Tools
{
    public class BucketTree
    {
        private float _max;
        private int _counter;
        private Node _root;
        private int _size;
        public BucketTree(int size)
        {
            _max = -1;
            _root = null;
            _counter = 0;
            _size = size;
        }

        public Node root
        {
            get{return _root;}
        }

        public void insert(float key,System.String element)
        {
            if(_counter >= _size && key >= _max)  return;
	        //Ist der Baum leer erstelle root
	        if(_root == null)
	        {
		        _root = new Node(key,null);
		        _root.add(element); 
		        _max = key;
		        _counter++;
		        return;
	        }
	        //Der baum ist nicht Leer
	        Node iter = root;
	        bool found = false;
	        //Suche nach den richtigen Fater Knoten 
	        //im binärbaum und erstelle einen neuen Kind Knoten
	        while(!found)
	        {
		        if(iter.key == key) found = true;
		        if(iter.key < key)
		        {
			        if(iter.right == null)
			        {
				        iter.right = new Node(key, iter);
				        found = true;
			        }
			        else iter = iter.right;
			
		        }
		        if(iter.key >key)
		        {
			        if(iter.left == null)
			        {
			        	iter.left = new Node(key, iter);
				        found = true;
			        }
			        else iter = iter.left;
		        }

        	}
	        iter.add(element);
            _counter++;
            if (_counter >= _size) removeMax();
            else
            {
                if (_max < key) _max = key;
               
            }

        }

        public List<String> toArray()
        {
            throw new System.NotImplementedException();
        }

        private void removeMax()
        {
            Node iter = root;
            //Gehe zum Knoten mit dem höchsten abstand
            while (iter.right != null)
                iter = iter.right;
            //entferne ein Element des Knotens
            iter.remove();
            _counter--;
            //ist der Knoten leer muss er entfernt werden
            if (iter.isEmpty())
            {
                //Bestimme FaterKnoten
                Node  parent = iter.parent;
                //Ist der Knoten der Root Knoten
                if (parent == null)
                {	//und er ist der einzige Knoten des Baumes
                    //enferne den root
                    if (iter.left == null)
                    {
                        iter = null;
                        return;
                    }
                    //ansonsten mache das Linke Kind
                    //den neuen root
                    _root = iter.left;
                    _max = root.key;
                    _root.parent = null;
                    return;
                }
                else//Is der Knoten kein root
                {
                    //Ist das linke Kind nicht belegt
                    if (iter.left == null)
                    {
                        //setze linkes Kind des Fater Knotens 
                        //als null pointer
                        parent.right = null;
                        _max = parent.key;
                    }
                    else//ansonsten
                    {
                        //Setze linkes Kind als neues linkes Kind 
                        //des Fater Knotens
                        iter = iter.left;
                        parent.right = iter;
                        iter.parent = parent;
                        //Suche den hösten abstand des unterbaums
                        while (iter.right != null)
                            iter = iter.right;
                        //uns setze es als neues Höcshtwert
                        _max = iter.key;
                    }
                }

            }
        }
    }
}
